package com.zhang.sort.cmp;


import com.zhang.sort.Sort;

/**
 * @author 张吉鑫
 * @Description 插入排序
 * @date 2021/4/12 20:51
 */
public class InsertionSort3<E> extends Sort<E> {
    /**
     * 插入排序的优化版
     * 假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2
     * 如果 v < m，去 [begin, mid) 范围内二分搜索
     * 如果 v > m，去 [mid + 1, end) 范围内二分搜索
     * 如果 v == m，直接返回mid
     */
    @Override
    protected void sort() {
        for (int i = 1; i < array.length; i++) {
            E element = array[i];
            int index = search(i);
            for (int i1 = i; i1 > index; i1--) {
                array[i1] = array[i1 - 1];
            }
            array[index] = element;
        }
    }

    /**
     * 二分查找需要插入位置的索引
     * @param end2 待排序的元素索引
     * @return 回返插入位置的索引
     */
    private int search(int end2){
        int begin = 0;
        int end = end2;
        while (begin < end){
            int mid = (end + begin) >> 1;
            if (cmpElement(array[mid], array[end2]) > 0){
                end = mid;
            }else{
                begin = mid + 1;
            }
        }
        return begin;

    }
}
